package 中等.搜索.深度优先搜索;

/**
 * 这里有一幅服务器分布图，服务器的位置标识在 m * n 的整数矩阵网格 grid 中，1 表示单元格上有服务器，0 表示没有。
 * 如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。
 * 请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/count-servers-that-communicate/description/
 */
public class 统计参与通信的服务器_1267 {

    public static void main(String[] args) {

    }

    /**
     * 深度优先搜索
     */
    public int countServers(int[][] grid) {
        int ans = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    int cnt = dfs(i, j, grid);
                    if (cnt > 1) {
                        ans += cnt;
                    }
                }
            }
        }

        return ans;
    }

    private int dfs(int i, int j, int[][] grid) {
        if (grid[i][j] == 0) {
            return 0;
        }
        int cnt = 1;
        grid[i][j] = 0;

        int m = grid.length;
        int n = grid[0].length;

        for (int nextJ = 0; nextJ < n; nextJ++) {
            cnt += dfs(i, nextJ, grid);
        }
        for (int nextI = 0; nextI < m; nextI++) {
            cnt += dfs(nextI, j, grid);
        }
        return cnt;
    }

}
